Round Overview
Discuss this match
The last SRM before TCO08 onsite finals became the most crowded TopCoder SRM ever as the limit on the number of participants was increased to 1750.
To finish in top3 in Division 1 it was enough to solve all three problems correctly, which was done by Petr, ACRush and Eryx, who finished first, second and third respectively. Because of many corner cases in the medium problem challenge phase was very fruitful, affecting final positions of many coders a lot.
In Division 2 nobody managed to solve the 1000-pointer correctly, so the top places were distributed between those, who were really fast on easy and medium and managed to make some successful challenges. This resulted in Al.Cash, taking the first place, followed by Duc, Landrew and a newcomer TheBlackParade.
DreamingAboutCarrots
Problem Details
Used as: Division Two - Level One:
Value | 250 |
Submission Rate | 739 / 833 (88.72%) |
Success Rate | 266 / 739 (35.99%) |
High Score | KnightOfTheSun for 249.01 points (1 mins 47 secs) |
Average Score | 197.21 (for 266 correct submissions) |
First approach
Under the given constraints it was possible to iterate through all lattice points that lie in a rectangle with corners (min(x1,x2),min(y1,y2)) and (max(x1,x2),max(y1,y2)) and check whether they lie on the given segment or not. This check can be done using cross product of vectors (you can see this tutorial by lbackstrom for more information about geometrical basics).
See this solution by Sainell for implementation of this approach.
Second approach
The second approach uses the following notion about lattice points, lying on the segment: neighbouring lattice points lie on the same distance from each other. Now consider the greatest common divisor of max(x1,x2) - min(x1,x2) and max(y1,y2) - min(y1,y2). Then there can be at most this value minus one lattice point, lying on the segment as described above.
This approach was used by KnightOfTheSun to achieve high score on this problem.
Used as: Division Two - Level Two:
Value | 500 |
Submission Rate | 260 / 833 (31.21%) |
Success Rate | 176 / 260 (67.69%) |
High Score | dlwjdans for 484.98 points (5 mins 1 secs) |
Average Score | 286.72 (for 176 correct submissions) |
Used as: Division One - Level One:
Value | 250 |
Submission Rate | 587 / 650 (90.31%) |
Success Rate | 549 / 587 (93.53%) |
High Score | ACRush for 246.54 points (3 mins 22 secs) |
Average Score | 187.12 (for 549 correct submissions) |
First approach
This problem could be solved by simple dynamic programming. Let’s construct FIELD diagrams row by row, starting from the first one (it will have index zero). Let dp[i][j] be the number of possible ways to extend a FIELD diagram that has all rows up to i-th already constructed and has the length of the last constructed row (the row number i - 1) equal to j. Then dp[fieldOrder][ANY_VALUE] should be taken equal to 1 (we have constructed a valid diagram) and dp[i][j] can be calculated as follows:
1 2 3 4 5 6 7 8 9 10 11 12
long[][] dp = new long[fieldOrder + 1][fieldOrder + 1]; for (int k = 0; k <= fieldOrder; k++) { dp[fieldOrder][k] = 1; } for (int i = fieldOrder - 1; i >= 0; i--) { for (int j = 0; j <= fieldOrder; j++) { dp[i][j] = 0; for (int k = 0; k <= Math.min(j, fieldOrder - i); k++) { dp[i][j] += dp[i + 1][k]; } } }
Now the answer for the problem will be dp[0][fieldOrder] - 1 as we have counted a digram, containing no boxes.
This approach was used by ACRush to achieve high score on this problem.
Second approach
The second approach was to notice that the number of FIELD diagrams of order n is equal to Cn+1 - 1, where Cn is the n-th Catalan number. See description of monotonic paths (analogs of FIELD diagrams) in the article for further explanation of why this formula works.
Used as: Division Two - Level Three:
Value | 1000 |
Submission Rate | 55 / 833 (6.60%) |
Success Rate | 0 / 55 (0.00%) |
High Score | No correct submissions |
Average Score | No correct submissions |
The shortest message appears somewhere in the given text, let it length be PeriodLen. Taking the first PeriodLen letters of the text as the message will give us the same text, so we can assume that the shortest message appears in the beginning of the text.
The hardest thing is to find this shortest message in linear time. Here KMP algorithm will help us a lot (see description of KMP algorithm in this tutorial). Let’s construct prefix function (which is called failure function in the tutorial) for the text and look its value on the last element of the text (let us call this value PrefLen, it gives us the length of the longest suffix of the text, which is at the same time its prefix). Now it is obvious that PrefLen is equal to TextLen - PeriodLen. This gives us solution shown below:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int textLength = text.length();
int[] prefixFunction = new int[textLength];
prefixFunction[0] = 0;
int cur = 0;
for (int i = 1; i < textLength; i++) {
while (cur > 0 && text.charAt(cur) != text.charAt(i)) {
cur = prefixFunction[cur - 1];
}
if (text.charAt(cur) == text.charAt(i)) {
cur++;
}
prefixFunction[i] = cur;
}
return textLength - prefixFunction[textLength - 1];
ParticleCollision
Problem Details
Used as: Division One - Level Two:
Value | 550 |
Submission Rate | 244 / 650 (37.54%) |
Success Rate | 72 / 244 (29.51%) |
High Score | gozman for 454.77 points (13 mins 36 secs) |
Average Score | 275.94 (for 72 correct submissions) |
First approach
The first approach is to find points of intersection of a cylinder x^2 + y^2 = 1 with the given line (using equations x = vx * t + x0 and y = vy * t + y0), solving quadratic equation for t, and then check whether solutions of this equation really lie on the given spiral. A case when vx and vy are both equal to zero should be considered separately.
See very clear implementation of this approach in gozman’s solution here.
Second approach
The second approach was to believe that intersections can happen only in points where z is half-integer. It turned out that under given constraints this was true. See discussion in forums here for some ideas about why this can be true for arbitrarily large input numbers.
I found four coders, who used this approach during the SRM: LayCurse, hhanger, crazyb0y and gerben.
Used as: Division One - Level Three:
Value | 950 |
Submission Rate | 11 / 650 (1.69%) |
Success Rate | 5 / 11 (45.45%) |
High Score | Petr for 539.64 points (30 mins 6 secs) |
Average Score | 430.14 (for 5 correct submissions) |
First of all let’s notice that we can consider only N-cool segments that contain exactly N lattice points, covered by the polygon, and also have their endpoints in lattice points (let’s call these segments N-really-cool segments) as long as all longer N-cool segments contain these segments as their part. So a point is N-cool if and only if it is an endpoint of some N-really-cool segment. This can be checked easily, because two points are endpoints of some N-really-cool segment if and only if their coordinates are equal modulo N - 1 (i.e. x1 mod (N - 1) = x2 mod (N - 1) and y1 mod (N - 1) = y2 mod (N - 1)).
Now if we find all lattice points, covered by the polygon, we are done, as we can easily check the property above. Because of the facts that the vertices of the polygon are given in random order, there can be duplicate points and three points, lying on the same line, it was really useful to construct convex hull of the given points first, rearranging them in some more useful order. Here comes the algorithm of finding a convex hull, constructing it as a union of the upper and the lower hull (see explanation of this algorithm in this tutoial by bmerry). Now points, covered by the polygon, can be found in a single line sweep pass, which studies every possible x coordinate, finding points with maximal and minimal y on this line and writing down all intermediate points.
You can see my implementation of this approach in the practice room.
Excercise
Prove that if there are more than N^2 lattice points, covered by the polygon, then there exists (N + 1)-cool segment.